package com.captjack.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/20 19:59
 * package com.captjack.search
 */
public class Bfs {

    /**
     * 上下左右四个方向
     */
    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     * bfs模版
     *
     * @param grid    地图
     * @param startX  开始x
     * @param startY  开始y
     * @param visited 是否访问过
     */
    public void bfsTemplate(char[][] grid, int startX, int startY, boolean[][] visited) {
        // 行、列
        int row = grid.length, col = grid[0].length;
        // 将初始点加入队列
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startX, startY});
        // 初始点置为已访问
        visited[startX][startY] = true;
        // 途径点
//        List<int[]> path = new LinkedList<>();
        // 走了几次
        int steps = -1;
        //
        while (!queue.isEmpty()) {
            // 步数加1
            steps++;
            int size = queue.size();
            //
            while (size-- > 0) {
                // 取出点
                int[] point = queue.poll();
                // 走四个方向
                for (int[] direction : DIRECTIONS) {
                    int nextX = point[0] + direction[0], nextY = point[1] + direction[1];
                    // 越界情况、或已经访问
                    if (nextX < 0 || nextX > row - 1 || nextY < 0 || nextY > col - 1 || visited[nextX][nextY]) {
                        continue;
                    }
                    // 此点置为已访问
                    visited[nextX][nextY] = true;
                    // 处理逻辑

                    // 将此点加入队列
                    queue.add(new int[]{nextX, nextY});
                }
            }
        }
        // 执行返回
    }

}
